package algorighm.class011;

// 给你两个 非空 的链表，表示两个非负的整数
// 它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字
// 请你将两个数相加，并以相同形式返回一个表示和的链表。
// 你可以假设除了数字 0 之外，这两个数都不会以 0 开头
// 测试链接：https://leetcode.cn/problems/add-two-numbers/
public class AddTwoNumbers {

	// 不要提交这个类
	public static class ListNode {
		public int val;
		public ListNode next;

		public ListNode(int val) {
			this.val = val;
		}

		public ListNode(int val, ListNode next) {
			this.val = val;
			this.next = next;
		}
	}

	static class Solution {

		// 也可以复用老链表
		// 不过这个实现没有这么做，都是生成的新节点(为了教学好懂)
		public static ListNode addTwoNumbers(ListNode h1, ListNode h2) {
			ListNode ans = null, cur = null;
			int carry = 0;
			for (int sum, val; // 声明变量
					h1 != null || h2 != null; // 终止条件
					h1 = h1 == null ? null : h1.next, // 每一步h1的跳转
					h2 = h2 == null ? null : h2.next // 每一步h2的跳转
					) {

				sum = (h1 == null ? 0 : h1.val)
						+ (h2 == null ? 0 : h2.val)
						+ carry;

				val = sum % 10;
				carry = sum / 10;
				if (ans == null) {
					ans = new ListNode(val);
					cur = ans;
				} else {
					cur.next = new ListNode(val);
					cur = cur.next;
				}
			}
			if (carry == 1) {
				cur.next = new ListNode(1);
			}
			return ans;
		}

	}
	/**
	 * 获取链表长度
	 */
	private int getLength(ListNode head) {
		int length = 0;
		while (head != null) {
			length++;
			head = head.next;
		}
		return length;
	}
	/**
	 * 优化后的两链表相加方法
	 * @param l1 第一个链表
	 * @param l2 第二个链表
	 * @return 相加结果的链表
	 */
	public ListNode addTwoNumbers2(ListNode l1, ListNode l2) {
		// 获取两个链表的长度
		int len1 = getLength(l1);
		int len2 = getLength(l2);

		// 确定长链表和短链表
		ListNode longList = len1 >= len2 ? l1 : l2;
		ListNode shortList = len1 >= len2 ? l2 : l1;

		ListNode dummyHead = new ListNode(0);
		ListNode current = dummyHead;
		int carry = 0;

		// 先处理两个链表都有的部分
		while (shortList != null) {
			int sum = longList.val + shortList.val + carry;
			carry = sum / 10;
			current.next = new ListNode(sum % 10);
			current = current.next;
			longList = longList.next;
			shortList = shortList.next;
		}

		// 处理长链表剩余部分，只在有进位时继续处理
		while (longList != null && carry != 0) {
			int sum = longList.val + carry;
			carry = sum / 10;
			current.next = new ListNode(sum % 10);
			current = current.next;
			longList = longList.next;
		}

		// 如果长链表还有剩余且无进位，直接连接剩余部分
		if (longList != null) {
			current.next = longList;
		}

		// 处理最后的进位
		if (carry > 0) {
			current.next = new ListNode(carry);
		}

		return dummyHead.next;
	}

	/**
	 * 辅助方法：创建链表
	 */
	public static ListNode createList(int[] nums) {
		ListNode dummyHead = new ListNode(0);
		ListNode current = dummyHead;
		for (int num : nums) {
			current.next = new ListNode(num);
			current = current.next;
		}
		return dummyHead.next;
	}

	/**
	 * 辅助方法：打印链表
	 */
	public static void printList(ListNode head) {
		ListNode current = head;
		while (current != null) {
			System.out.print(current.val + " ");
			current = current.next;
		}
		System.out.println();
	}

	public static void main(String[] args) {
		AddTwoNumbers solution = new AddTwoNumbers();

		// 测试用例1: 342 + 465 = 807
		ListNode l1 = createList(new int[]{2, 4, 3});
		ListNode l2 = createList(new int[]{5, 6, 4});
		ListNode result = solution.addTwoNumbers2(l1, l2);
		printList(result); // 输出: 7 0 8

		// 测试用例2: 9999999 + 9999 = 10009998
		ListNode l3 = createList(new int[]{9,9,9,9,9,9,9});
		ListNode l4 = createList(new int[]{9,9,9,9});
		result = solution.addTwoNumbers2(l3, l4);
		printList(result); // 输出: 8 9 9 9 0 0 0 1

		// 测试用例3: 1234 + 876 = 2110
		ListNode l5 = createList(new int[]{4,3,2,1});
		ListNode l6 = createList(new int[]{6,7,8});
		result = solution.addTwoNumbers2(l5, l6);
		printList(result); // 输出: 0 1 1 2
	}
}
